package com.itheima.datastructure.binarysearchtree.binarytree;

import java.util.Arrays;

/*
根据前序，后需遍历结果构造二叉树
 */
public class E09Leetcode105 {
    public TreeNode buildTree(int [] preOrder,int [] inOrder){
        if(preOrder.length==0){
            return null;
        }
        //创建根结点
        int rootValue=preOrder[0];
        TreeNode root=new TreeNode(rootValue);
        //划分左右子树
        for(int i=0;i<inOrder.length;i++){
            if(inOrder[i]==rootValue){
                //0-i-1 左子树
                //i+1-inorder。length-1 右子树
                int[] inLeft= Arrays.copyOfRange(inOrder,0,i);
                int [] inRight=Arrays.copyOfRange(inOrder,i+1,inOrder.length);

                int [] preLeft=Arrays.copyOfRange(preOrder,1,i+1);
                int [] preRight=Arrays.copyOfRange(preOrder,i+1,preOrder.length);

                root.left=buildTree(preLeft,inLeft);
                root.right=buildTree(preRight,inRight);
                break;
            }
        }
        return root;
    }

}
